package com.yequan.leetcode.array.thirdMax_414;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * //给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
 * //
 * // 示例 1:
 * //
 * //
 * //输入: [3, 2, 1]
 * //
 * //输出: 1
 * //
 * //解释: 第三大的数是 1.
 * //
 * //
 * // 示例 2:
 * //
 * //
 * //输入: [1, 2]
 * //
 * //输出: 2
 * //
 * //解释: 第三大的数不存在, 所以返回最大的数 2 .
 * //
 * //
 * // 示例 3:
 * //
 * //
 * //输入: [2, 2, 3, 1]
 * //
 * //输出: 1
 * //
 * //解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。
 * //存在两个值为2的数，它们都排第二。
 * //
 * // Related Topics 数组
 *
 * @author : Administrator
 * @date : 2020/4/18
 */
public class ThirdMax {

    public static void main(String[] args) {
        int[] num1 = {3, 2, 1};
        int[] num2 = {2, 2, 3, 1};
        ThirdMax thirdMax = new ThirdMax();
        int ans = thirdMax.thirdMax(num2);
        System.out.println(ans);
    }

    /**
     * 1.统计出现的次数
     * 2.将数组存入大顶堆中
     *
     * @param nums
     * @return
     */
    public int thirdMax(int[] nums) {
        if (null == nums || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }

        Map<Integer, Integer> countMap = new HashMap<>(16);
        Arrays.stream(nums).forEach(num -> countMap.put(num, countMap.getOrDefault(num, 0) + 1));

        if (countMap.size() == 1) {
            return ((int) countMap.keySet().toArray()[0]);
        }
        if (countMap.size() == 2) {
            return Math.max(((int) countMap.keySet().toArray()[0]), ((int) countMap.keySet().toArray()[1]));
        }


        PriorityQueue<Integer> heap = new PriorityQueue<>((n1, n2) -> n2 - n1);
        for (int i = 0; i < nums.length; i++) {
            heap.offer(nums[i]);
        }

        int a = 0;
        while (heap.size() > 0) {
            Integer num = heap.peek();
            if (a == 2) {
                return num;
            }
            Integer count = countMap.get(num);
            for (int i = 0; i < count; i++) {
                heap.poll();
            }
            a++;
        }
        return 0;
    }

}
